package simple;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/5/10 13:57
 */
public class No88_合并两个有序数组 {
    public static void main(String[] args) {
        Solution88 solution88 = new Solution88();
        //int[] nums1 = new int[]{-10,-10,-9,-9,-9,-8,-8,-7,-7,-7,-6,-6,-6,-6,-6,-6,-6,-5,-5,-5,-4,-4,-4,-3,-3,-2,-2,-1,-1,0,1,1,1,2,2,2,3,3,3,4,5,5,6,6,6,6,7,7,7,7,8,9,9,9,9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        //int m = 55;
        //int[] nums2 =new int[]{-10,-10,-9,-9,-9,-9,-8,-8,-8,-8,-8,-7,-7,-7,-7,-7,-7,-7,-7,-6,-6,-6,-6,-5,-5,-5,-5,-5,-4,-4,-4,-4,-4,-3,-3,-3,-2,-2,-2,-2,-2,-2,-2,-1,-1,-1,0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,9,9,9,9};
        //int n = 99;

        int[] nums1 = new int[]{2, 3, 3, 7, 9, 0, 0, 0, 0, 0, 0, 0, 0};
        int m = 5;
        int[] nums2 = new int[]{0, 0, 1, 5, 13};
        int n = 5;


        solution88.merge(nums1, m, nums2, n);
        for (int num : nums1) {
            System.out.println(num);
        }
    }
}


class Solution88 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //3个指针合作,不使用额外空间
        int A = m - 1;
        int B = n - 1;
        int current = m + n - 1;
        while (A >= 0 && B >= 0) {
            if (nums1[A] > nums2[B]) {
                nums1[current] = nums1[A];
                A--;
            } else {
                nums1[current] = nums2[B];
                B--;
            }
            current--;
        }

        if (A < 0) {
            //把nums2加进去
            for (int i = current; i >= 0; i--) {
                nums1[i] = nums2[B--];
            }
        }
    }
}


    //public void merge(int[] nums1, int m, int[] nums2, int n) {
    //    //3个指针合作
    //    int A = 0;
    //    int B = 0;
    //    int current = 0;
    //    int[] extra = nums1.clone();
    //
    //    while (A < m && B < n) {
    //        if (extra[A] < nums2[B]) {
    //            nums1[current] = extra[A];
    //            A++;
    //        } else {
    //            nums1[current] = nums2[B];
    //            B++;
    //        }
    //        current++;
    //    }
    //
    //    if (A == m) {
    //        //说明nums2可以继续
    //        for (int i = current; i < m + n; i++) {
    //            nums1[i] = nums2[B++];
    //        }
    //    }else if (B == n) {
    //        //说明nums1可以继续
    //        for (int i = current; i < m + n; i++) {
    //            nums1[i] = extra[A++];
    //        }
    //    }
    //}

    //public void merge(int[] nums1, int m, int[] nums2, int n) {
    //    //鸡贼法
    //    List<Integer> result = new ArrayList<>();
    //    //nums1遍历
    //    for (int i = 0; i < m; i++) {
    //        result.add(nums1[i]);
    //    }
    //
    //    //num2遍历
    //    for (int i = 0; i < n; i++) {
    //        result.add(nums2[i]);
    //    }
    //
    //    //list排序
    //    result.sort(new Comparator<Integer>() {
    //        @Override
    //        public int compare(Integer o1, Integer o2) {
    //            return o1.compareTo(o2);//去研究一下为啥有bug,从底层分析
    //        }
    //    });
    //
    //    //遍历list,机智地刷回去
    //    for (int i = 0; i < m + n; i++) {
    //        nums1[i] = result.get(i);
    //    }
    //}